//给你一个整数数组 nums 。nums 中，子数组的 范围 是子数组中最大元素和最小元素的差值。 
//
// 返回 nums 中 所有 子数组范围的 和 。 
//
// 子数组是数组中一个连续 非空 的元素序列。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,2,3]
//输出：4
//解释：nums 的 6 个子数组如下所示：
//[1]，范围 = 最大 - 最小 = 1 - 1 = 0 
//[2]，范围 = 2 - 2 = 0
//[3]，范围 = 3 - 3 = 0
//[1,2]，范围 = 2 - 1 = 1
//[2,3]，范围 = 3 - 2 = 1
//[1,2,3]，范围 = 3 - 1 = 2
//所有范围的和是 0 + 0 + 0 + 1 + 1 + 2 = 4 
//
// 示例 2： 
//
// 
//输入：nums = [1,3,3]
//输出：4
//解释：nums 的 6 个子数组如下所示：
//[1]，范围 = 最大 - 最小 = 1 - 1 = 0
//[3]，范围 = 3 - 3 = 0
//[3]，范围 = 3 - 3 = 0
//[1,3]，范围 = 3 - 1 = 2
//[3,3]，范围 = 3 - 3 = 0
//[1,3,3]，范围 = 3 - 1 = 2
//所有范围的和是 0 + 0 + 0 + 2 + 0 + 2 = 4
// 
//
// 示例 3： 
//
// 
//输入：nums = [4,-2,-3,4,1]
//输出：59
//解释：nums 中所有子数组范围的和是 59
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 1000 
// -10⁹ <= nums[i] <= 10⁹ 
// 
//
// 
//
// 进阶：你可以设计一种时间复杂度为 O(n) 的解决方案吗？ 
// Related Topics 栈 数组 单调栈 👍 43 👎 0

package leetcode.editor.cn;

import java.util.*;

public class _2104_SumOfSubarrayRanges {
    public static void main(String[] args) {
        int[] arr = new int[] {1,5,6,0,7,4,9,3};
        int[] index = new int[] {0,1,2,3,4,0,5,1,2,6,7};

        String tel = "";
        for (int i : index) {
            tel += arr[i];
        }
        System.out.println("联系方式： " + tel);





//        Solution solution = new _2104_SumOfSubarrayRanges().new Solution();
//        int[] nums = {1,2,3};
////        int[] nums = {1,2,3,2,3,1,2,1,3};
//        System.out.print("Nums: ");
//        System.out.println(Arrays.toString(nums));
//        System.out.println(solution.subArrayRanges(nums));
    }

    class Solution {
        public long subArrayRanges(int[] nums) {
            int n = nums.length;
            int[] minLeft = new int[n];
            int[] minRight = new int[n];
            int[] maxLeft = new int[n];
            int[] maxRight = new int[n];
            Deque<Integer> minStack = new ArrayDeque<Integer>();
            Deque<Integer> maxStack = new ArrayDeque<Integer>();
            for (int i = 0; i < n; i++) {
                while (!minStack.isEmpty() && nums[minStack.peek()] > nums[i]) {
                    minStack.pop();
                }
                minLeft[i] = minStack.isEmpty() ? -1 : minStack.peek();
                minStack.push(i);

                // 如果 nums[maxStack.peek()] == nums[i], 那么根据定义，
                // nums[maxStack.peek()] 逻辑上小于 nums[i]，因为 maxStack.peek() < i
                while (!maxStack.isEmpty() && nums[maxStack.peek()] <= nums[i]) {
                    maxStack.pop();
                }
                maxLeft[i] = maxStack.isEmpty() ? -1 : maxStack.peek();
                maxStack.push(i);
            }
            minStack.clear();
            maxStack.clear();
            for (int i = n - 1; i >= 0; i--) {
                // 如果 nums[minStack.peek()] == nums[i], 那么根据定义，
                // nums[minStack.peek()] 逻辑上大于 nums[i]，因为 minStack.peek() > i
                while (!minStack.isEmpty() && nums[minStack.peek()] >= nums[i]) {
                    minStack.pop();
                }
                minRight[i] = minStack.isEmpty() ? n : minStack.peek();
                minStack.push(i);

                while (!maxStack.isEmpty() && nums[maxStack.peek()] < nums[i]) {
                    maxStack.pop();
                }
                maxRight[i] = maxStack.isEmpty() ? n : maxStack.peek();
                maxStack.push(i);
            }

            long sumMax = 0, sumMin = 0;
            for (int i = 0; i < n; i++) {
                sumMax += (long) (maxRight[i] - i) * (i - maxLeft[i]) * nums[i];
                sumMin += (long) (minRight[i] - i) * (i - minLeft[i]) * nums[i];
            }
            return sumMax - sumMin;
        }
    }


    class Solution5 {
        public long subArrayRanges(int[] nums) {
            int n = nums.length;
            int[] minLeft = new int[n];
            int[] minRight = new int[n];
            int[] maxLeft = new int[n];
            int[] maxRight = new int[n];
            Deque<Integer> minStack = new ArrayDeque<Integer>();
            Deque<Integer> maxStack = new ArrayDeque<Integer>();
            for (int i = 0; i < n; i++) {
                while (!minStack.isEmpty() && nums[minStack.peek()] > nums[i]) {
                    minStack.pop();
                }
                minLeft[i] = minStack.isEmpty() ? -1 : minStack.peek();
                minStack.push(i);

                // 如果 nums[maxStack.peek()] == nums[i], 那么根据定义，
                // nums[maxStack.peek()] 逻辑上小于 nums[i]，因为 maxStack.peek() < i
                while (!maxStack.isEmpty() && nums[maxStack.peek()] <= nums[i]) {
                    maxStack.pop();
                }
                maxLeft[i] = maxStack.isEmpty() ? -1 : maxStack.peek();
                maxStack.push(i);
            }
            minStack.clear();
            maxStack.clear();
            for (int i = n - 1; i >= 0; i--) {
                // 如果 nums[minStack.peek()] == nums[i], 那么根据定义，
                // nums[minStack.peek()] 逻辑上大于 nums[i]，因为 minStack.peek() > i
                while (!minStack.isEmpty() && nums[minStack.peek()] >= nums[i]) {
                    minStack.pop();
                }
                minRight[i] = minStack.isEmpty() ? n : minStack.peek();
                minStack.push(i);

                while (!maxStack.isEmpty() && nums[maxStack.peek()] < nums[i]) {
                    maxStack.pop();
                }
                maxRight[i] = maxStack.isEmpty() ? n : maxStack.peek();
                maxStack.push(i);
            }

            long sumMax = 0, sumMin = 0;
            for (int i = 0; i < n; i++) {
                sumMax += (long) (maxRight[i] - i) * (i - maxLeft[i]) * nums[i];
                sumMin += (long) (minRight[i] - i) * (i - minLeft[i]) * nums[i];
            }
            return sumMax - sumMin;
        }
    }


    class Solution4 {
        public long subArrayRanges(int[] nums) {
            int[] minRight = new int[nums.length];
            int[] maxRight = new int[nums.length];
            Deque<Integer> stMin = new ArrayDeque<>();
            Deque<Integer> stMax = new ArrayDeque<>();
            for (int i = 0; i < nums.length; i++) {
                while (!stMin.isEmpty() && nums[i] < nums[stMin.peekLast()]) {
                    minRight[stMin.removeLast()] = i;
                }
                while (!stMax.isEmpty() && nums[i] >= nums[stMax.peekLast()]) {
                    maxRight[stMax.removeLast()] = i;
                }
                stMin.addLast(i);
                stMax.addLast(i);
            }
            while (!stMin.isEmpty()) {
                minRight[stMin.removeLast()] = nums.length;
            }
            while (!stMax.isEmpty()) {
                maxRight[stMax.removeLast()] = nums.length;
            }

            int[] minLeft = new int[nums.length];
            int[] maxLeft = new int[nums.length];
            for (int i = nums.length - 1; i >= 0; i--) {
                while (!stMin.isEmpty() && nums[i] <= nums[stMin.peekLast()]) {
                    minLeft[stMin.removeLast()] = i;
                }
                while (!stMax.isEmpty() && nums[i] > nums[stMax.peekLast()]) {
                    maxLeft[stMax.removeLast()] = i;
                }
                stMin.addLast(i);
                stMax.addLast(i);
            }
            while (!stMin.isEmpty()) {
                minLeft[stMin.removeLast()] = -1;
            }
            while (!stMax.isEmpty()) {
                maxLeft[stMax.removeLast()] = -1;
            }

            long sumMin = 0;
            long sumMax = 0;
            for (int i = 0; i < nums.length; i++) {
                sumMin += (long)(minRight[i] - i) * (i - minLeft[i]) * nums[i];
                sumMax += (long)(maxRight[i] - i) * (i - maxLeft[i]) * nums[i];
            }


            return sumMax - sumMin;
        }
    }

    // 这个还是官方给的暴力解法
    class Solution3 {
        public long subArrayRanges(int[] nums) {
            long res = 0;
            for (int i = 0; i < nums.length; i++) {
                int min = Integer.MAX_VALUE;
                int max = Integer.MIN_VALUE;
                for (int j = i; j < nums.length; j++) {
                    min = Math.min(min, nums[j]);
                    max = Math.max(max, nums[j]);

                    res += max - min;
                }
            }
            return res;
        }
    }

    // 这个是官方给的暴力解法
    class Solution2 {
        public long range = 0;
        public long subArrayRanges(int[] nums) {
            long res = 0;
            for (int i = 0; i < nums.length; i++) {
                long min = Long.MAX_VALUE;
                long max = Long.MIN_VALUE;
                for (int j = i; j < nums.length; j++) {
                    max = Math.max(max, nums[j]);
                    min = Math.min(min, nums[j]);
                    res += (max - min);
                }
            }
            return res;
        }

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    // 这里做成了每一个子数组，没想到题目要求的是只有连续的
    class Solution1 {
        public long range = 0;
        public long subArrayRanges(int[] nums) {
            int count = 1 << nums.length;
            long sum = 0;
            for (int i = 0; i < count; i++) {
                long[] num = new long[nums.length];
                int index = 0;
                for (int j = 0; j < nums.length; j++) {
                    if (((i >> j) & 1) == 1) {
                        num[index++] = nums[j];
                    }
                }
                sum += arrayRanges(num, index);
            }

            System.out.println(count);

            return sum;
        }

        public long arrayRanges(long[] nums, int index) {
            long max = nums[0];
            long min = nums[0];


//            System.out.println();

            for (int i = 0; i < index; i++) {
                max = Math.max(max, nums[i]);
                min = Math.min(min, nums[i]);
            }
            System.out.print((max - min) + ": ");

            System.out.print("Every list: ");
            for (int i = 0; i < index; i++) {
                System.out.print(nums[i] + " ");
            }
            System.out.println();
            return max - min;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
